package de.dopichaj.labrador.search.prune;

import java.util.Collection;
import java.util.SortedSet;
import java.util.TreeSet;

import org.apache.log4j.Logger;

import de.dopichaj.labrador.search.hit.Hit;
import de.dopichaj.labrador.search.hit.HitComparator;
import de.dopichaj.labrador.search.hit.HitHierarchyTree;


/**
 * Implements pruning by selecting the highest scoring node in any path.
 * The result is suitable for submission to INEX's focussed sub-task.
 */
public class ScoreBasedPruner implements ResultTreePruner {

    private static final Logger log = Logger.getLogger(ScoreBasedPruner.class);
    
    public void prune(HitHierarchyTree tree) {
        
        SortedSet<Hit> sortedHits = new TreeSet<Hit>(new HitComparator(HitComparator.SORT_BY_SCORE));
        Collection<Hit> allHits = tree.getAllHits();
        sortedHits.addAll(allHits);
        
        // while there are overlapping nodes in the tree
        while (hasOverlappingNodes(tree)) {
            
            // find the hit with the highest score
            // ... first remove hits that have been removed from the result set
            final Hit bestHit = sortedHits.first();
            if (log.isDebugEnabled()) {
                log.debug("Will add " + bestHit);
            }
            
            // remove all ancestors from result
            Hit parent = tree.getParent(bestHit);
            while (parent != null) {
                if (log.isDebugEnabled()) {
                    log.debug("Removing " + parent);
                }
                sortedHits.remove(parent);
                tree.removeFromResults(parent);
                parent = tree.getParent(parent);
            }                
            
            // remove all descendants from result
            removeDescendants(tree, bestHit, sortedHits);
            
            // add hit to result set
            sortedHits.remove(bestHit);
        }
    }
    
    private boolean hasOverlappingNodes(HitHierarchyTree tree) {
        
        // for all hits in the current result
        for (Hit hit : tree.generateHitList()) {
            
            if (log.isDebugEnabled()) {
                log.debug("Checking " + hit + " for overlapping hits.");
            }
            
            // check ancestors
            Hit parent = tree.getParent(hit);
            while (parent != null) {
                if (tree.isInResults(parent)) {
                    return true;
                }
                parent = tree.getParent(parent);
            }                
            
            log.debug("-> No overlapping nodes.");
        }
        
        // if we got here, there were no overlaps
        return false;
    }
    
    private void removeDescendants(HitHierarchyTree tree, Hit hit, SortedSet<Hit> sortedHits) {
        for (Hit child : tree.getUnsortedChildren(hit)) {
            tree.removeFromResults(child);
            sortedHits.remove(child);
            removeDescendants(tree, child, sortedHits);
        }
    }

    public String getDescription() {
        return "score-based focused pruner";
    }
}
/*
Copyright (c) 2005-2007 Philipp Dopichaj

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/